The invention relates to a device for carrying out a division of a dividend A by a divisor D formed by "n" words expressing a base "b" so as to obtain a quotient Q and a remainder R.
Such a device finds its major applications in fields where divisions of great numbers are required. There is, however, a preferred field of application for the invention: the field of microcircuit boards using the RSA encoding process. This process, which is described in the U.S. Pat. No. 4,405,829 of Rivest, Shamir and Adleman, 1978, is a system with a public key "e". It is based on the difficulty of splitting up a large number "N", which is the product of two original numbers "p" and "q", into factors.
The basic operation of this encoding system can be described as follows. The message to be encoded is given the form of a chain of separate numbers in blocks M of fixed length, smaller than N. Each block presents a cryptogram C by means of an exponent "e" which may be known to the public and which is a number which divides neither "p-1" nor "q-1", carrying out the following operation: EQU C=M.sup.e (mod N)
in which (mod N) indicates that the operation is carried out in accordance with a modulo N.
To re-establish the message, the receiver must know a secret exponent "d" and carry out the operation: EQU M=C.sup.d (mod N), i.e.: EQU M=M.sup.de (mod N)
A presently used number of binary elements constituting N is 512, which corresponds to approximately 155 decimal figures, then a length of the order of 256 binary elements each is taken for "p" and "q". The devices carrying out this encoding process use the Chinese Remainder Theory which renders it possible to transform an exponential with to 512 binary elements into two exponentials of 256 elements for each of these factors. The factors "p", "q" in their turn are substituted for "N" and the exponentiation operations are carried out in accordance with the modules "p" and "q".
European Patent Application No. 0,443,679 (PHQ 90.002) describes the manner in which these exponentiations are carried out. These teachings have been carried into practice in the microcontroller 83C852 manufactured by Philips. The modulo exponentiations are carried out with normalized numbers. This normalization consists in that three bytes are reserved which are used in the subsequent calculations. This application nevertheless proposes means for the case in which the numbers are not normalized. This implies in practice that it is necessary to provide two kinds of calculation processes, a first process for normalized numbers and another for non-normalized numbers. On the one hand this other process is much less adapted to the structure of the microcontroller and may lead to a lengthy calculation time, and on the other hand the presence of two processes takes up much space in the program memory.
This is where the invention finds a major application, i.e. in rendering possible the normalization of all proposed numbers N. These are multiplied by a normalization coefficient, after which a division is carried out by this same coefficient at the end of the exponentiation processes.